package com.hanxiaozhang.greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;

/**
 * 〈一句话功能简述〉<br>
 * 〈拼接字符串，返回最小字典序〉
 *
 * @author hanxinghua
 * @create 2021/9/22
 * @since 1.0.0
 */
public class LowestString {

    public static void main(String[] args) {

        String[] array1 = {"c","b","qf","ab","h"};
        String[] array2 = {"c","b","qf","ab","h"};

        System.out.println(lowestString1(array1));
        System.out.println(lowestString2(array2));

    }

    /**
     * 给定一个由字符串组成的数组array，必须把所有的字符串拼接起来，
     * 返回所有可能的拼接结果中，字典序最小的结果。
     *
     * @param array
     * @return
     */
    public static String lowestString1(String[] array) {
        if (array == null || array.length == 0) {
            return "";
        }
        // 全部可能性
        ArrayList<String> all = new ArrayList<>();
        // 使用过的字符
        HashSet<Integer> use = new HashSet<>();
        // 记录每一个使用过字符
        process(array, use, "", all);
        // 循环比较，获取最小
        String lowest = all.get(0);
        for (int i = 1; i < all.size(); i++) {
            if (all.get(i).compareTo(lowest) < 0) {
                lowest = all.get(i);
            }
        }
        return lowest;
    }

    private static void process(String[] array, HashSet<Integer> use, String path, ArrayList<String> all) {
        // 使用过个数等于数组长度，证明已经使用完全
        if (use.size() == array.length) {
            all.add(path);
        } else {
            // 循环拼接
            for (int i = 0; i < array.length; i++) {
                if (!use.contains(i)) {
                    use.add(i);
                    process(array, use, path + array[i], all);
                    use.remove(i);
                }
            }
        }
    }

    /**
     * 给定一个由字符串组成的数组array，必须把所有的字符串拼接起来，
     * 返回所有可能的拼接结果中，字典序最小的结果。
     *
     * @param array
     * @return
     */
    public static String lowestString2(String[] array) {
        if (array == null || array.length == 0) {
            return "";
        }
        Arrays.sort(array, new MyComparator());
        String res = "";
        for (int i = 0; i < array.length; i++) {
            res += array[i];
        }
        return res;
    }

    /**
     * 比较器
     */
    public static class MyComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            return (a + b).compareTo(b + a);
        }
    }


}
